package org.example;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 遇到子数组/子串相关的问题，你只要能回答出来以下几个问题，就能运用滑动窗口算法：
 * 1、什么时候应该扩大窗口？
 * 2、什么时候应该缩小窗口？
 * 3、什么时候应该更新答案？
 */
// https://labuladong.online/algo/essential-technique/sliding-window-framework/
public class SlidingWindow {
    // 滑动窗口可以归为快慢双指针，一快一慢两个指针前后相随，中间的部分就是窗口。
    // 滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组

    // 滑动窗口框架概览
    // 如果用暴力解的话，你需要嵌套 for 循环这样穷举所有子数组，时间复杂度是O(N^2)
    /*
    * for (int i = 0; i < nums.length; i++) {
        for (int j = i; j < nums.length; j++) {
            // nums[i, j] 是一个子数组
        }
      }
    * */
    // 滑动窗口算法技巧的思路也不难，就是维护一个窗口，不断滑动，然后更新答案，该算法的大致逻辑如下：
    /*
        int left = 0, right = 0;
        while (right < nums.size()) {
            // 增大窗口
            window.addLast(nums[right]);
            right++;

            while (window needs shrink) {
                // 缩小窗口
                window.removeFirst(nums[left]);
                left++;
            }
        }
     */
    // 基于滑动窗口算法框架写出的代码，时间复杂度是 O(N)，比嵌套 for 循环的暴力解法效率高。
    // 所以今天我就写一套滑动窗口算法的代码框架，我连再哪里做输出 debug 都给你写好了，以后遇到相关的问题，
    // 你就默写出来如下框架然后改三个地方就行，保证不会出 bug。

    // 滑动窗口模板
    /*public void slidingWindow(String s) {
        // 用合适的数据结构记录窗口中的数据，根据具体场景变通
        // 比如说，我想记录窗口中元素出现的次数，就用map
        // 如果我想记录窗口中的元素和，就可以只用一个int
        Object window = ...
        int left = 0;
        int right = 0;
        while (right < s.length()) {
            // c是将移入窗口的字符
            char c = s[right];
            window.add(c);
            // 增大窗口
            right++;
            // 进行窗口内数据的一些列更新
            ...

            // *** debug 输出的位置 ***
            // 注意在最终的解法代码中不要 print
            // 因为 IO 操作很耗时，可能导致超时
            printf("window: [%d, %d)\n", left, right);
            // ***********************

            // 判断左侧窗口是否收缩
            while (left < right && window needs shrink){
                // d是将移出窗口的字符
                char d = s[left];
                window.remove(d);
                left++;
                // 进行窗口内数据的一系列更新
                ...
            }
        }

        框架中两处 ... 表示的更新窗口数据的地方，在具体的题目中，你需要做的就是往这里面填代码逻辑。
        而且，这两个 ... 处的操作分别是扩大和缩小窗口的更新操作，等会你会发现它们操作是完全对称的。
    }*/

    // 76. 最小覆盖子串
    // 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
    // 示例 1：
    // 输入：s = "ADOBECODEBANC", t = "ABC"
    // 输出："BANC"
    // 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
    static class MinWindow {
        // 滑动窗口算法的思路是这样：
        //1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
        // 为什么要「左闭右开」区间
        // 理论上你可以设计两端都开或者两端都闭的区间，但设计为左闭右开区间是最方便处理的。
        // 因为这样初始化 left = right = 0 时区间 [0, 0) 中没有元素，但只要让 right 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。
        // 如果你设置为两端都开的区间，那么让 right 向右移动一位后开区间 (0, 1) 仍然没有元素；如果你设置为两端都闭的区间，
        // 那么初始区间 [0, 0] 就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。
        // 2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
        // 3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。
        // 同时，每次增加 left，我们都要更新一轮结果。
        // 4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头
        // 这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。
        // 左右指针轮流前进，窗口大小增增减减，就好像一条毛毛虫，一伸一缩，不断向右滑动，这就是「滑动窗口」这个名字的来历。
        /*public String minWindow(String s, String t) {
            // 首先，初始化 window 和 need 两个哈希表，记录窗口中的字符和需要凑齐的字符：
            // 记录window中的字符出现次数
            HashMap<Character, Integer> window = new HashMap<>();
            // 记录所需的字符出现次数
            HashMap<Character, Integer> need = new HashMap<>();
            for(int i = 0; i < t.length(); i++){
                char c = t.charAt(i);
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
            // 然后，使用 left 和 right 变量初始化窗口的两端，不要忘了，区间 [left, right) 是左闭右开的，
            // 所以初始情况下窗口没有包含任何元素：
            int left = 0;
            int right = 0;
            // 其中 valid 变量表示窗口中满足 need 条件的字符个数，
            // 如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T。
            int valid = 0;
            while(right < s.length()){
                // c是将移入窗口的字符
                char c = s.charAt(right);
                // 右移窗口
                right++;
                // 进行窗口内数据的一系列更新
                // 如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；
                // 当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。
                // ...
            }
        }*/

        public String minWindow(String s, String t) {
            Map<Character, Integer> need = new HashMap<>();
            Map<Character, Integer> window = new HashMap<>();
            for (int i = 0; i < t.length(); i++) {
                char c = t.charAt(i);
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
            int left = 0;
            int right = 0;
            int valid = 0;
            // 记录最小覆盖子串的起始索引及长度
            int start = 0;
            int len = Integer.MAX_VALUE;
            while (right < s.length()) {
                // c是将移入窗口的字符
                char c = s.charAt(right);
                // 扩大窗口
                right++;
                // 进行窗口内数据的一些列更新
                if (need.containsKey(c)) {
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if (window.get(c).equals(need.get(c))) {
                        valid++;
                    }
                }
                // 判断左侧窗口是否要收缩
                while (valid == need.size()) {
                    // 在这里更新最小覆盖子串
                    if (right - left < len) {
                        start = left;
                        len = right - left;
                    }
                    // d是将移出窗口的字符
                    char d = s.charAt(left);
                    // 缩小窗口
                    left++;
                    // 进行窗口内数据的一系列更新
                    if (need.containsKey(d)) {
                        if (window.get(d).equals(need.get(d))) {
                            valid--;
                        }
                        window.put(d, window.get(d) - 1);
                    }
                }
            }
            return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
        }

        // 567. 字符串的排列
        // 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。
        // 换句话说，s1 的排列之一是 s2 的 子串 。
        // 示例 1：
        // 输入：s1 = "ab" s2 = "eidbaooo"
        // 输出：true
        // 解释：s2 包含 s1 的排列之一 ("ba").
        static class CheckInclusion{
            // 判断 s 中是否存在 t 的排列
            public boolean checkInclusion(String t, String s) {
                Map<Character, Integer> need = new HashMap<>();
                Map<Character, Integer> window = new HashMap<>();
                for(char c : t.toCharArray()){
                    need.put(c, need.getOrDefault(c, 0) + 1);
                }
                int left = 0;
                int right = 0;
                int valid = 0;
                while(right < s.length()){
                    char c = s.charAt(right);
                    right++;
                    // 进行窗口内数据的一些列更新
                    if (need.containsKey(c)){
                        window.put(c, window.getOrDefault(c, 0) + 1);
                        if (window.get(c).intValue() == need.get(c).intValue()){
                            valid++;
                        }
                    }
                    // 判断左侧窗口是否要收缩
                    while(right - left >= t.length()){ // 因为是排列，所以长度应该是一样的。
                        // 在这里判断是否找到了合法子串
                        if (valid == need.size()){ // 当发现valid == need.size()时，就说明窗口中就是一个合法的排列，所以立即返回。
                            return true;
                        }
                        char d = s.charAt(left);
                        left++;
                        if (need.containsKey(d)){
                            if (need.get(d).intValue() == window.get(d).intValue()){
                                valid--;
                            }
                            window.put(d, window.get(d)-1);
                        }
                    }
                }
                // 未找到符合条件的子串
                return false;
            }
        }
    }

    // 438. 找到字符串中所有字母异位词
    // 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
    // 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
    // 示例 1:
    // 输入: s = "cbaebabacd", p = "abc"
    // 输出: [0,6]
    // 解释:
    // 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
    // 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
    static class FindAnagrams{
        public List<Integer> findAnagrams(String s, String t) {
            Map<Character, Integer> need = new HashMap<>();
            Map<Character, Integer> window = new HashMap<>();
            for(char c : t.toCharArray()){
                need.put(c, need.getOrDefault(c, 0) + 1);
            }
            int left = 0;
            int right = 0;
            int valid = 0;
            // 记录结果
            List<Integer> res = new ArrayList<>();
            while(right < s.length()){
                char c = s.charAt(right);
                right++;
                if (need.containsKey(c)){
                    window.put(c, window.getOrDefault(c, 0) + 1);
                    if (need.get(c).intValue() == window.get(c).intValue()){
                        valid++;
                    }
                }

                // 判断左侧窗口是否要收缩
                while(right - left >= t.length()){
                    // 当窗户口符合条件时，把起始索引加入res
                    if (valid == need.size()){
                        res.add(left);
                    }
                    char d = s.charAt(left);
                    left++;
                    if (need.containsKey(d)){
                        if (window.get(d).intValue() == need.get(d).intValue()){
                            valid--;
                        }
                        window.put(d, window.get(d) - 1);
                    }
                }
            }
            return res;
            // 跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入 res 即可。
        }
    }

    // 最长无重复子串
    // 3. 无重复字符的最长子串
    // 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
    // 示例 1:
    // 输入: s = "abcabcbb"
    // 输出: 3
    // 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
    static class LengthOfLongestSubstring{
        public int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> window = new HashMap<>();
            int left = 0;
            int right = 0;
            // 记录结果
            int res = 0;
            while(right < s.length()){
                char c = s.charAt(right);
                right++;
                // 进行窗口内数据的一系列更新
                window.put(c, window.getOrDefault(c, 0) + 1);
                while(window.get(c) > 1){
                    char d = s.charAt(left);
                    left++;
                    // 进行窗口内数据的一系列更新
                    window.put(d, window.get(d) - 1);
                }
                res = Math.max(res, right - left);
            }
            return res;
        }
    }

    // 回顾一下，遇到子数组/子串相关的问题，你只要能回答出来以下几个问题，就能运用滑动窗口算法：
    //1、什么时候应该扩大窗口？
    //2、什么时候应该缩小窗口？
    //3、什么时候应该更新答案？


    // 代码随想录算法
    /*
        // 滑动窗口算法伪码框架
        void slidingWindow(String s) {
            // 用合适的数据结构记录窗口中的数据，根据具体场景变通
            // 比如说，我想记录窗口中元素出现的次数，就用 map
            // 如果我想记录窗口中的元素和，就可以只用一个 int
            Object window = ...

            int left = 0, right = 0;
            while (right < s.length()) {
                // c 是将移入窗口的字符
                char c = s[right];
                window.add(c)
                // 增大窗口
                right++;
                // 进行窗口内数据的一系列更新
                ...

                // *** debug 输出的位置 ***
                // 注意在最终的解法代码中不要 print
                // 因为 IO 操作很耗时，可能导致超时
                printf("window: [%d, %d)\n", left, right);
                // ***********************

                // 判断左侧窗口是否要收缩
                while (left < right && window needs shrink) {
                    // d 是将移出窗口的字符
                    char d = s[left];
                    window.remove(d)
                    // 缩小窗口
                    left++;
                    // 进行窗口内数据的一系列更新
                    ...
                }
            }
        }
    */
    // 1. 最小覆盖子串
    // 为什么要【左闭右开】区间
    // 因为这样初始化left = right = 0时区间[0, 0)中没有元素，但只要让right向右移动（扩大）一位，区间[0, 1)就包含了一个元素0了。
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;
        int valid = 0; // 其中valid变量表示窗口中满足need条件的字符个数，如果valid和need.size的大小相同，则说明窗口已满足条件，已经完全覆盖了串T。
        // 记录最小覆盖子串的起始索引及长度
        int start = 0;
        int len = Integer.MAX_VALUE;
        while (right < s.length()) {
            // c是将移入窗口的字符
            char c = s.charAt(right);
            // 扩大窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d是将移出窗口的字符
                char d = s.charAt(left);
                // 缩小窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    // 2. 字符串排列
    // 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
    public boolean checkInclusion(String t, String s) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0;
        int right = 0;
        int valid = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).intValue() == need.get(c).intValue()) {
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            // 本题移动left缩小窗口的时机时窗口大小大于t.length()时，因为排列
            while (right - left >= t.length()) {
                // 在这里判断是否找到了合法子串
                if (valid == need.size()) {
                    return true;
                }
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).intValue() == need.get(d).intValue()) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 未找到符合条件的子串
        return false;
    }

    // 3. 找所有字母异位词
    public List<Integer> findAnagrams(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;
        int valid = 0;
        // 记录结果
        List<Integer> res = new ArrayList<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while (right - left >= t.length()) {
                // 当窗口符合条件时，把起始索引加入到res
                if (valid == need.size()) {
                    res.add(left);
                }
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return res;
    }

    // 4. 最长无重复子串
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0;
        int right = 0;
        // 记录结果
        int res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 判断左侧窗口是否要收缩
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一些列更新
                window.put(d, window.get(d) - 1);
            }
            res = Math.max(res, right - left);
        }
        return res;
    }
}